1. Field of the Invention
This invention relates to the field of data decoding. More particularly, this invention relates to the field of the decoding of data composed of interleaved first type code words and second type code words, in which each first type code word defines a runlength of constant values preceding a variable value defined by a following second type code word.
2. Description of the Prior Art
It is known to provide data encoding techniques which generate data in the form of interleaved first type code words and second-.type code words. An example of such an encoding technique is that proposed by the Joint Photographic Experts Group (JPEG) and currently under review by the International Standards Organisation.
The JPEG standard is intended for the compression of image data in computer systems. The image data is initially transformed into the spatial frequency domain by discrete cosine transformation. The ac spatial components have a distinctly different character to the dc spatial components. The ac spatial components are subject to runlength coding to exploit the long runs of zero values in this data. The dc spatial components do not show this characteristic.
The JPEG standard proposes the use of first and second type code words with the following syntax for the ac data, i.e. EQU [RUNLENGTH, SIZE], [AMPLITUDE]
In this case RUNLENGTH is the number of zeros preceding a nonzero value. SIZE is the number of bits that will be needed to represent the non-zero value. AMPLITUDE is the non-zero value and has a bit length equal to the specified by SIZE.
Consider the following data stream of image data, EQU . . . ,0,0,0,7,0,0,0,0,0,0,11,0,0,0 . . .
The middle portion, comprising six zeros followed by a non-zero value of 11, would be encoded with the value of RUNLENGTH=6 representing the six zeros. The non-zero value of 11 will require four bits to represent it, and so SIZE=4. The value of AMPLITUDE is 11, or 1011 in binary. Thus, the sequence 0,0,0,0,0,0,11 is encoded as [6,4], [11]. The [6,4] is a first type code word and the [11] is a second type code word.
Whilst the JPEG standard yields good compression performance, it gives rise to decoding problems in some circumstance. The JPEG standard is primarily intended for image display in computer systems. Computer systems can carry out essentially non-real time decoding of the compressed data by reading it into memory and then scanning through it to reconstruct the non-compressed data as a separate, nonsynchronous operation. Such an approach to decoding does not work well in real time video systems.
One problem is that the volume of image data in a video system is much higher. Whereas a computer system can store and then process a single image without processing speed limitations becoming noticeable, a video system typically has to process the equivalent of thirty such images every second to keep pace with the video data stream.
In addition, there is the problem that the decoding of the compressed data should produce an output data stream with a constant data rate matching the video data rate of the apparatus that will subsequently display the data. Accordingly, the system must be able to cope with the fact that the ratio between the number of bits of input data to the number of bits of decoded data generated is not constant. The ratio can very significantly depending on factors such as the information content of each image, or how well the compression and coding techniques match a particular part of the data stream.
It is an object of the invention to provide a high speed data decoder capable of producing a constant data rate output.